/**
 * 广度优先
 * @param {number[][]} grid
 * @return {number}
 */
export var orangesRotting = function (grid) {
  const queue = []
  // 先找出已经腐烂的橘子个数, 和没有放橘子的个数
  let empty = 0
  let rotten = 0
  for (let i = 0; i < grid.length; i++) {
    for (let j = 0; j < grid[0].length; j++) {
      if (grid[i][j] === 2) {
        rotten++
        queue.push([i, j])
      }
      if (grid[i][j] === 0) {
        empty++
      }
    }
  }
  // 如果盒子是空的，直接返回 0
  if (empty === grid.length * grid[0].length) return 0
  // 如果一开始就没有坏橘子，并且盒子不为空，直接返回 -1
  if (rotten === 0) return -1

  // 从已经腐烂的橘子开始，每次查找周围的橘子，并将其设置为腐烂
  let step = 0
  const dir = [
    [-1, 0],
    [1, 0],
    [0, -1],
    [0, 1],
  ]
  while (queue.length > 0) {
    // 每轮都清空队列，代表经过一分钟
    const size = queue.length
    for (let i = 0; i < size; i++) {
      const [row, col] = queue[i]
      for (const [dRow, dCol] of dir) {
        const newRow = row + dRow
        const newCol = col + dCol
        if (
          newRow >= 0 &&
          newRow < grid.length &&
          newCol >= 0 &&
          newCol < grid[0].length &&
          grid[newRow][newCol] === 1
        ) {
          grid[newRow][newCol] = 2
          queue.push([newRow, newCol])
          rotten++
        }
      }
    }
    queue.splice(0, size)
    step++
  }
  return rotten + empty === grid.length * grid[0].length ? step - 1 : -1
}
